package com.zhanghp.class037;

import com.zhanghp.common.TreeNode;

import static java.lang.Math.*;

/**
 * 搜索二叉树上寻找两个节点的最近公共祖先<br/>
 * 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
 *
 * @author zhanghp
 * @since 2024/4/19 15:12
 */
public class Code02_LowestCommonAncestorBinarySearch {

    static class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            // root从上到下
            // 如果先遇到了p，说明p是答案
            // 如果先遇到了q，说明q是答案
            // 如果root在p~q的值之间，不用管p和q谁大谁小，只要root在中间，那么此时的root就是答案
            // 如果root在p~q的值的左侧，那么root往右移动
            // 如果root在p~q的值的右侧，那么root往左移动
            while (root.val != p.val && root.val != q.val) {
                // 搜索二叉树性质，若p,q在root两侧，则root就是祖先
                if (min(p.val, q.val) < root.val && max(p.val, q.val) > root.val) {
                    break;
                }
                // 由于上面判断完了，所以root只能在p，q的左，或者右
                root = root.val < min(p.val, q.val) ? root.right : root.left;
            }
            return root;
        }
    }
}
